package notes.java.sort;

/**
 * 希尔排序（插入排序的升级版）
 * 1、对于一个数组，定义一个间隔，如gap=n，将间隔为n的数排序
 * 2、间隔缩小为原来的一倍，gap=n/2，再把间隔为n/2的数排序
 * 3、间隔再缩小一倍排序，直到gap=1，排序完成
 *
 */
public class S4_ShellSort {

	public static void main(String[] args) {
		
		// 定义一个数组
		int[] num = { 5, 9, 4, 8, 2, 1, 0, 7, 3, 6, 10, 19, 11, 20, 14, 17, 15 };
		
		// 定义一个间隔，每次缩小为原来的一倍(一般定义数组的长度的一半)
		for(int gap=num.length/2; gap>0; gap/=2) {
			
			// 插入排序
			for(int i=gap; i<num.length; i++) {
				
				// 分别和前面的数比较，小就移到前面
				for(int j=i; j>gap-1; j-=gap) {
					if(num[j] < num[j-1]) {
						int temp = num[j];
						num[j] = num[j-1];
						num[j-1] = temp;
					}
				}
			}
			
			print(num, gap);
		}
		
	}
	
	/** 打印输出*/
	private static void print(int[] num, int n) {
		// 输出
		for (int i = 0; i < num.length; i++) {
			if(i == n) {
				System.out.print("↑" + num[i] + " ");
			} else {
				System.out.print(num[i] + " ");
			}
		}
		System.out.println();
	}

}

